package com.leetcode.题库;

import com.leetcode.common.model.ListNode;
import com.leetcode.common.utils.ListNodeUtils;

/**
 * @author 覃国强
 * @date 2022-06-30 10:44
 */
public class 题库_0092_反转链表II {


  public static void main(String[] args) {
    ListNode head = ListNodeUtils.generateListNode(new int[]{1, 2, 3, 4, 5});
    ListNodeUtils.print(head);
    Solution solution = new Solution();
    ListNode node = solution.reverseBetween(head, 2, 4);
    ListNodeUtils.print(node);
  }

  static
  class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
      if (left >= right) {
        return head;
      }
      ListNode dummy = new ListNode();
      dummy.next = head;

      ListNode leftTail = dummy;
      for (int i = 1; i < left; ++i) {
        leftTail = leftTail.next;
      }

      ListNode prev = null;
      ListNode node = leftTail.next;
      ListNode tail = node;


      int num = right - left;
      for (int i = 0; i <= num; ++i) {
        ListNode next = node.next;
        node.next = prev;
        prev = node;
        node = next;
      }

      leftTail.next = prev;
      tail.next = node;

      return dummy.next;
    }
  }

}
